import Heap from 'heap'
import Jimp from 'jimp'
import { color_diff } from './color'

class Node {
  constructor ({ x, y, endDistance = 0, startDistance = 0, color = [] }) {
    this.x = x
    this.y = y
    this.color = color
    this.endDistance = endDistance // 与终点的距离
    this.startDistance = startDistance // 与起点的实际距离
    this.colorDistance = 0 // 颜色距离
    this.distance = endDistance + startDistance
    this.passed = false // 该节点是否已探索完毕
    this.isQueue = false // 该节点否已经在队列中
    this.parent = null // 记录从哪个节点过来，方便回溯
    this.nextNodes = null
  }
}

async function waitFrame () {
  return new Promise((resolve, reject) => {
    requestAnimationFrame(resolve)
  })
}

/**
 * 取节点
 *
 * @param {Node[]} nodes
 * @param {*} x
 * @param {*} y
 * @returns {Node}
 */
function getNode(nodes, bitmap, x, y, width) {
  if (x >= 0 && y >= 0 && x < width && y < bitmap.height) {
    const i = y * width + x
    let node = nodes[i]
    if (node) {
      return node
    } else {
      node = new Node({ x, y, color: getColor(bitmap, x, y) })
      nodes[i] = node
      return node
    }
  } else {
    return null
  }
}

/**
 * 取两节点距离
 *
 * @param {Node} nodeA
 * @param {Node} nodeB
 */
function getDistance (nodeA, nodeB) {
  const x = Math.abs(nodeB.x - nodeA.x)
  const y = Math.abs(nodeB.y - nodeA.y)
  return (x + y)
}

/**
 * 取下一个移动点集合
 *
 * @param {*} m
 * @param {*} current
 * @returns
 */
function getNextNodes(nodes, bitmap, { x, y }, width) {

  const upNode = getNode(nodes, bitmap, x - 1, y, width)
  const downNode = getNode(nodes, bitmap, x + 1, y, width)
  const leftNode = getNode(nodes, bitmap, x, y - 1, width)
  const rightNode = getNode(nodes, bitmap, x, y + 1, width)

  return [ upNode, downNode, leftNode, rightNode ]
}

function getColor (bitmap, x, y) {
  const { width, data } = bitmap
  const i = y * width + x
  const bitmapIndex = i * 4
  return [data[bitmapIndex], data[bitmapIndex + 1], data[bitmapIndex + 2]]
}

/**
 * 直接回溯，构建路径
 *
 * @param {Node} endNode
 */
function backtrack_path (endNode) {
  let paths = []
  let node = endNode

  while (node) {
    paths.push(node)
    node = node.parent
  }

  return paths.map(node => {
    return [node.x, node.y]
  }).reverse()
}



/**
 * 计算路径
 * @param {Bitmap} bitmap 
 * @param {Number[]} start
 * @param {Number} end
 * @param {Number} MAX_DIFF 
 */
async function solveMaze (bitmap, start, end, MAX_DIFF) {
  async function renderSeekPath (drawNodes, forceRender = false) {
    const { seekPathBuffer } = window.vm
    if ((seekPathBuffer != 0 && drawNodes.length > seekPathBuffer) || forceRender) {
      window.dispatchEvent(new CustomEvent('node-step', {
        detail: drawNodes
      }))
      await waitFrame()
      return []
    } else {
      return drawNodes
    }
  }

  const { width, height } = bitmap
  let nodes = new Array(width * height)
  let drawNodes = []
  let checkCount = 0
  
  // 等待探索的节点集合
  let queue = new Heap((a, b) => a.distance - b.distance)

  let startNode = getNode(nodes, bitmap, start[0], start[1], width)
  queue.push(startNode)

  while (!queue.empty()) {
    if (window.vm.seeking === false) {
      break
    }
    const node = queue.pop()
    checkCount++
    node.passed = true

    drawNodes.push(node)
    drawNodes = await renderSeekPath(drawNodes)

    let nextNodes = getNextNodes(nodes, bitmap, node, width)
    for (let i = nextNodes.length - 1; i >= 0; i--) {
      let n = nextNodes[i]
      if (n && n.passed === false) {
        n.parent = node
        n.startDistance = node.startDistance + 1 // 更新与起点的距离
        n.endDistance = getDistance(n, { x: end[0], y: end[1] })
        n.colorDistance = color_diff(startNode.color, n.color) * MAX_DIFF
        n.distance = n.startDistance + n.endDistance + n.colorDistance

        if (!n.isQueue) {
          queue.push(n)
          n.isQueue = true
        }

        if (n.endDistance === 0) {
          console.log(`solve! check point count: ${checkCount}`)
          drawNodes = renderSeekPath(drawNodes, true)
          return {
            paths: backtrack_path(n),
            checkCount
          }
        }
      }
    }
  }

  throw Error('无法到达终点')
}

async function goSolve (imgSrc, start, end, MAX_DIFF = 150) {
  let { bitmap } = await Jimp.read(imgSrc)

  let result = await solveMaze(bitmap, start, end, MAX_DIFF)
  return result
}

export {
  goSolve
}
